package class17;

import java.util.ArrayList;
import java.util.List;

/**
 * @author YZY
 * @since 2022/8/17 14:58
 * 打印一个字符串的全部排列
 * <a href="https://leetcode.cn/problems/permutation-i-lcci/">面试题 08.07. 无重复字符串的排列组合</a>
 * <a href="https://leetcode.cn/problems/permutation-ii-lcci/">面试题 08.08. 有重复字符串的排列组合</a>
 */
public class Code04_PrintAllPermutations {

    // 经典回溯写法，常数时间较大，可以优化
    public static List<String> allPermutations1(String str) {
        List<Character> arr = new ArrayList<>();
        for (char s : str.toCharArray()) {
            arr.add(s);
        }
        String s = "";
        List<String> result = new ArrayList<>();
        process1(arr, s, result);
        return result;
    }

    private static void process1(List<Character> arr, String s, List<String> result) {
        if (arr.isEmpty()) {
            result.add(s);
            return;
        }
        for (int i = 0; i < arr.size(); ++i) {
            Character cur = arr.remove(i);
            process1(arr, s + cur, result);
            arr.add(i, cur);
        }
    }

    // 优化写法，交换逻辑，有重复
    public static List<String> allPermutations2(String str) {
        char[] arr = str.toCharArray();
        List<String> result = new ArrayList<>();
        process2(arr, result, 0);
        return result;
    }

    private static void process2(char[] arr, List<String> result, int index) {
        if (index == arr.length) {
            result.add(String.valueOf(arr));
            return;
        }
        for (int i = index; i < arr.length; ++i) {
            swap(arr, i, index);
            process2(arr, result, index + 1);
            swap(arr, i, index);
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 优化写法，交换逻辑，没有重复
    public static List<String> allPermutations3(String str) {
        char[] arr = str.toCharArray();
        List<String> result = new ArrayList<>();
        process3(arr, result, 0);
        return result;
    }

    private static void process3(char[] arr, List<String> result, int index) {
        if (index == arr.length) {
            result.add(String.valueOf(arr));
            return;
        }
        boolean[] visits = new boolean[256];
        for (int i = index; i < arr.length; ++i) {
            if (!visits[arr[i]]) {
                visits[arr[i]] = true;
                swap(arr, i, index);
                process3(arr, result, index + 1);
                swap(arr, i, index);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(allPermutations1("acc"));
        System.out.println(allPermutations2("acc"));
        System.out.println(allPermutations3("acc"));
    }

}
